The present invention relates to a medium access control (MAC) protocol, known as an xe2x80x9con-demand multiple access fair queuingxe2x80x9d system, for application in a wireless communications network system. In particular, the invention relates to a method for managing queue overload in time and frequency division half- and full-duplex multiple access wireless communications networks employing the xe2x80x9con-demand multiple access fair queuingxe2x80x9d system.
Wireless services, such as cellular voice and data and wireless LANs, are expected to enjoy rapid growth in the years to come. Third generation wireless networks designed to carry multimedia traffic are currently under intensive research, with the major goals being to provide seamless communications, high bandwidth availability, and guaranteed Quality of Service (QoS) without any location or mobility constraints.
FIG. 1 depicts a prior art wired network for data exchange. Shown are the three existing business entities whose equipment, working in concert, is typically utilized today to provide remote internet access through modems to user computers. User computers 2 and user modems 4 constitute end systems. The first business entity shown in FIG. 1 is the telephone company (telco) that owns and operates the dial-up plain old telephone system (POTS) or integrated services data network (ISDN). The telco provides a transmission medium in the form a of public switched telephone network (PSTN) 6 over which bits or packets can flow between users and the other two business entities.
The second business entity shown in FIG. 1 is the internet service provider (ISP). The ISP deploys and manages one or more points of presence (POPs) 8 in its service area, to which end users connect for network service. An ISP typically establishes a POP in each major local calling area in which the ISP expects to have subscribers. The POP 8 converts message traffic from the PSTN 6 into a digital form to be carried over intranet backbone 10, which is either owned by the ISP or leased from an intranet backbone provider such as MCI, Inc. An ISP typically leases fractional or full T1 or T3 lines from the telco for connectivity to the PSTN. The POPs 8 and the ISP""s media data center 14 are connected together over the intranet backbone 10 through router 12A. The data center 14 houses the ISP""s web servers, mail servers, accounting, and registration servers, enabling the ISP to provide web content, e-mail, and web hosting services to end users. Future value-added services may be added by deploying additional types of servers in the data center 14. The ISP maintains router 12A in order to connect to public internet backbone 20. In the existing model for remote access, end users typically have service relationships with both their telco and their ISP, usually getting separate bills from each. End users access the ISP and, through the ISP, public internet 20, by dialing the nearest POP and running a communication protocol known as the Internet Engineering Task Force (IETF) point-to-point (PPP) protocol.
The third business entity shown in FIG. 1 is a private corporation which owns and operates its own private intranet 18, accessed through router 12B. Corporate employees may remotely access corporate network 18 (e.g., from home or while on the road) by making POTS/ISDN calls to corporate remote access server 16 and running the IETF PPP protocol. For corporate access, end users pay only for the cost of connecting to corporate remote access server 16. The ISP is not involved. The private corporation maintains router 12B in order to connect an end user to either corporate intranet 18 or public internet 20.
End users currently pay the telco for both the cost of making phone calls and the cost of a phone line into their home. End users also must pay the ISP for access to the ISP""s network and services. Today, internet service providers offer internet access services, web content services, e-mail services, content-hosting services, and roaming to end users. Because of low margins and lack of market segmentation based on features and price, ISPs are looking for value-added services to improve margins. In the short term, equipment vendors want to be able to offer solutions to ISPs that enable them to offer faster access, virtual private networking (the ability to use public networks securely as private networks and connect to intranets), roaming consortiums, push technologies, and specific Quality of Service. In the longer term, it is desired to offer voice over internet and mobility. ISPs will then be able to use these value-added services to escape from the low margin straitjacket. Many of these value-added services fall into the category of network services and can be offered only through the network infrastructure equipment. Other value-added services fall into the category of application services which require support from the network infrastructure, while still others do not require any support from the network infrastructure. In particular, services like faster access, virtual private networking, roaming, mobility, voice, Quality of Service, and QoS-based accounting all need enhanced network infrastructure.
Wireless communications networks have the advantage of being able to extend the reach of wired networks. However, achievable bandwidths in wireless networks frequently lag behind those available in wired networks. Wired broadband systems like asynchronous transfer mode (ATM) are capable of providing services with different QoS (e.g., constant bit rate (CBR), variable bit rate (VBR), and available bit rate (ABR)) for enhanced support of multimedia applications. It is desired to extend such services to wireless networks. Research on merging ATM and wireless networks is therefore currently underway in many institutions and research laboratories. Many fundamental issues, affecting everything from the access layer to the transport layer, are being studied. Besides use of ATM as a transmission format at the air interface of a wireless network, ATM is also being considered for the wired infrastructure of cellular systems. Such a wired ATM infrastructure would be capable of supporting multiple access air interface technologies (e.g., CDMA, TDMA, etc.).
In a wireless network that supports multimedia traffic, an efficient channel access protocol needs to be maximize the utilization of the limited wireless spectrum while still supporting the quality of service requirements of all traffic. Several well-known channel access protocols are currently used in wireless data systems, such as Slotted Aloha, PRMA, etc. Slotted Aloha is a simple protocol but, because it does not attempt to avoid or resolve collisions between data users, its theoretical capacity is just 0.37. In addition, Slotted Aloha is unsuitable for efficient transmission of variable-length packets.
Reservation-based protocols attempt to avoid and resolve collisions by dynamically reserving channel bandwidth for users needing to send packets. Typically, in such protocols a channel is divided into slots which are grouped into frames of N slots. A slot can be further subdivided into k minislots. Normally, N1 of the slots will be used for reservation purposes while the remaining Nxe2x88x92N1 slots are data slots. The users that need to send packets send a reservation request packet in one of the M=N1*k minislots. If the reservation request packet is successful, then the user will be allocated a certain number of data slots until the user or the base station releases the reservation. If the reservation request packet is not successful, the user will use a conflict resolution method to retransmit the reservation request until it is successfully transmitted.
A multiple access protocol for hybrid fiber-coax networks has been proposed by Doshi et al. in xe2x80x9cA Broadband Multiple Access Protocol for STM, ATM, and Variable Length Data Services on Hybrid Fiber-Coax Networks,xe2x80x9d Bell Labs Technical Journal, Summer 1996, pp. 36-65. While sharing many issues with the wireless environment, this protocol does not completely address the unique problems encountered in the design of a wireless access scheme, such dealing with retransmissions over an error-prone wireless link and establishment of the transmission power level needed to ensure proper packet delivery. While this scheme does propose the idea of contention reservation slots, it does not provide a flexible scheme wherein the number of contention slots can be varied dynamically based on queue size information.
Karol et al have proposed a xe2x80x9cDistributed-Queuing Request Update Multiple Accessxe2x80x9d scheme (DQRUMA) [Karol et al xe2x80x9cAn efficient demand-assignment multiple access protocol for wireless packet (ATM) networks,xe2x80x9d Wireless Networks 1, pp. 267-279, 1995]. This wireless access scheme does not allow new users to contend for bandwidth during the conflict resolution period or utilize the reservation slot contention success rate during the previous round to adjust backoff time. This scheme also does not utilize a fair queuing technique, and hence does not make use of service tags to fairly allocate bandwidth between competing sources.
An important topic in designing a channel access protocol is selection of the scheduling techniques used to set the transmission order of uplink and downlink packets. A number of schedulers which are all variations on fair queuing have been proposed for wired networks [See, e.g., S. J., Golestani, xe2x80x9cA Self-Clocked Fair Queuing Scheme For Broadband Applicationsxe2x80x9d, Proceedings of IEEE Infocom, 1994; Parekh and Gallagher, xe2x80x9cA Generalized Processor Sharing Approach To Flow Control In Integrated Services Networks: The Single Node Casexe2x80x9d, IEEE/ACM Transactions On Networking, 1(3): 344-357, June 1993; L. Zhang, xe2x80x9cVirtual Clock Algorithmxe2x80x9d, Proceedings of ACM Symposium, pp 1224-1231, 1992]. These all have the effect of providing access to a share of bandwidth as if each service class has its own server at its given rate.
The Weighted Fair Queuing scheme of Parekh and Gallagher is difficult to implement, so the Self-Clocked Fair Queuing (SCFQ) scheme was proposed by Golestani . For SCFQ, the service tag is computed as;                               F          k          i                =                                            L              k              i                                      r              k                                +                      max            ⁡                          (                                                F                  k                                      i                                          -                      1                                                                      ,                                                      u                    ^                                    ⁡                                      (                                          a                      k                      i                                        )                                                              )                                                          (        1        )            
where û(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the Ith packet of class k. Packets are then served in the order of these tag values. The algorithm of Golestani is designed for wired networks, however, and must be modified if it is to function in a wireless environment. In particular the algorithm of Golestani does not address either how to handle transmission scheduling when the server (base station) does not have complete information about the size of the queues because they are remotely located or how to handle retransmission of lost packets.
Lu et al (University of Illinois) have proposed an xe2x80x9cIdealized Weighted Fair Queuingxe2x80x9d algorithm [Lu et al, xe2x80x9cFair Scheduling in Wireless Packet Networks,xe2x80x9d Sigcom ""97] that is designed to accommodate the special needs of wireless networks. This scheme requires full knowledge of the channel state (i.e. whether it is good or bad), something that is not generally available in a real network. It also does not change the service tags of packets that do not transmit successfully, leading to a complicated retransmission process, and drops packets from lagging flow, rather than only when there is a buffer overflow.
Another wireless access scheme, proposed by R. Kautz in xe2x80x9cA Distributed Self-Clocked Fair Queuing Architecture For Wireless ATM Networksxe2x80x9d, 1997 International Symposium on Personal Indoor and Mobile Radio Communications, utilizes a polling system instead of a reservation and piggybacked reservation approach. Polling schemes generally have poorer performance in terms of delay and bandwidth usage as compared to reservation access schemes. In addition, the scheme of Kautz changes service tag values only for those packets transmitted in error, causing the QoS at all remotes to suffer because the packets of all the remotes are delayed by retransmission of the lost packet.
The present invention is an aspect of an on-demand multiple access (ODMA) method with a fair queuing Q) service discipline (referred to as ODMAFQ) for efficient utilization of the limited bandwidth available in wireless communications networks. In this method, a bursty source sends a channel access packet to reserve bandwidths for future transmissions whenever a packet has arrived at an empty queue, while a constant bit rate source is made to undergo contention only once, during connection set-up. A distributed self-clocked fair queuing service discipline is used to determine the transmission order of various uplink sources, allowing diverse QoS to be provided.
In the method of the invention, if the downlink/uplink buffer occupancy of the network has exceeded a high threshold, the base station determines if this is caused by a specific remote host or by a group of remote hosts. If it is caused by a specific remote host, the base station normally sends a flow control signal to the remote host to prevent it from sending more data. In addition, the base station may reduce the bandwidth shares allocated to any remote hosts that have indicated during the connection set-up that they can tolerate a variable allocated bandwidth. The base station may alternatively elect to disconnect other remote hosts if the remote experiencing bad performance is of a higher priority.
If the measured downlink frame error rates for many remote hosts are seen to be increasing, then the base station may be experiencing an increased interference level from other access points. When there is congestion due to an increased interference level, the base station may elect to disconnect those remote hosts that permit service interruption in order that more bandwidth may be allocated to the remaining users. If a majority of all associated remote hosts experience high uplink frame error rates, the base station may instead send a xe2x80x9ccongestedxe2x80x9d signal to a wireless hub which can coordinate the actions of other access points, such as by sending signals to these access points to inhibit them from admitting new users and dropping lower priority users.
Short packets queued up for so long in either the uplink or downlink queue at the base station that they exceed the time-to-live value allocated will be thrown away, resulting in an increase in packet loss rate due to the processing bottleneck at the base station. Under such an overload situation, the base station may elect to temporarily disconnect some users of a lower priority. Alternatively, instead of disconnecting remote hosts having a lower priority, they may be redirected to other nearby base stations that have a lower load.
In a particular embodiment of a method for overload control in a network employing On-Demand Multiple Access Fair Queuing, an uplink Frame Error Rate (FER), an average uplink bit rate, a burstiness factor of uplink traffic, and a packet loss rate are measured at the base station for each remote host. Similarly, a downlink Frame Error Rate, an average downlink bit rate, the burstiness factor of the downlink traffic, and the packet loss rate is measured at each remote host and then each downlink FER is sent to the base station. If an overload condition exits, flow-control messages are sent between at least one of the remote hosts and the base station in order to control data flow. Packets at the base station having a delay exceeding a time-to-live threshold are then discarded, and connections with a Frame Error Rate that has exceeded a threshold for a specified time and that have indicated that their connections can be interrupted are disconnected. Other combinations of the possible actions discussed would also be suitable; the exact combination being decided by the base station depending on the particular congestion conditions observed in the network.
It is a general object of the present invention to provide a remote host with bandwidth on demand in a wireless communication network. It is a particular object of the present invention to provide a method to efficiently manage overload situations in such a wireless communications network.